Let D be a directed graph with vertex set V and order n. An anti-directedhamiltonian cycle H in D is a hamiltonian cycle in the graph underlying D suchthat no pair of consecutive arcs in H form a directed path in D. Ananti-directed 2-factor in D is a vertex-disjoint collection of anti-directedcycles in D that span V. It was proved in [3] that if the indegree and theoutdegree of each vertex of D is greater than (9/16)n then D contains ananti-directed hamilton cycle. In this paper we prove that given a directedgraph D, the problem of determining whether D has an anti-directed 2-factor isNP-complete, and we use a proof technique similar to the one used in [3] toprove that if the indegree and the outdegree of each vertex of D is greaterthan (24/46)n then D contains an anti-directed 2-factor.
展开▼
